package features.advance.leetcode.array.medium;

import java.util.*;

/**
 *  剑指 Offer II 119. 最长连续序列
 *
 *  难度：中等
 *
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [100,4,200,1,3,2]
 * 输出：4
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
 * 示例 2：
 *
 * 输入：nums = [0,3,7,2,5,8,4,6,0,1]
 * 输出：9
 *
 *
 * 提示：
 *
 * 0 <= nums.length <= 104
 * -109 <= nums[i] <= 109
 *
 *
 * 进阶：可以设计并实现时间复杂度为 O(n) 的解决方案吗？
 *
 *
 *
 * 注意：本题与主站 128 题相同： https://leetcode-cn.com/problems/longest-consecutive-sequence/
 *
 * @author LIN
 * @date 2021-08-30
 */
public class Offer2_119 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            @Override
            public int longestConsecutive(int[] nums) {
                Set<Integer> set = new HashSet<>(16);

                for (int num : nums) {
                    set.add(num);
                }
                int longStreak = 0;
                for (int num : nums) {
                    if(!set.contains(num-1)){
                        int currentNum = num;
                        int currentStreak = 1;
                        while (set.contains(currentNum+1)){
                            currentStreak++;
                            currentNum++;
                        }
                        longStreak = Math.max(longStreak,currentStreak);
                    }
                }
                return longStreak;
            }
        };
        // 2ms 性能极佳
        // [100,4,200,31,33,32]这个测试用例不通过
       /* solution = new Solution(){
            @Override
            public int longestConsecutive(int[] nums) {
                if(nums==null||nums.length==0) return 0;
                if(nums.length==1) return 1;
                int min=Integer.MAX_VALUE,max=Integer.MIN_VALUE;
                for(int num:nums){
                    if(num<min){
                        min=num;
                    }
                    if(num>max){
                        max=num;
                    }
                }
                int[] minArray=new int[nums.length];
                int[] maxArray=new int[nums.length];
                int minLeft=min,minRight=min+nums.length-1,maxLeft=max-nums.length+1,maxRight=max;
                for(int num:nums){
                    if(num>=minLeft&&num<=minRight){
                        minArray[num-minLeft]=1;
                    }
                    if(num>=maxLeft&&num<=maxRight){
                        maxArray[num-maxLeft]=1;
                    }
                }
                int minLen=0,maxLen=0,minCur=0,maxCur=0;

                for(int i=0;i<nums.length;i++){
                    if(minArray[i]==1){
                        minCur++;
                        minLen=Math.max(minCur,minLen);
                    }else{
                        minCur=0;
                    }

                    if(maxArray[i]==1){
                        maxCur++;
                        maxLen=Math.max(maxCur,maxLen);
                    }else{
                        maxCur=0;
                    }
                }
                return Math.max(minLen,maxLen);
            }
        };*/
        int[] nums = {100,4,200,31,32,33};
        int res = solution.longestConsecutive(nums);
        System.out.println(res);

    }

    static class Solution {
        public int longestConsecutive(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }
            // key: nums[i], vlaue: i
            Map<Integer, Integer> map = new HashMap<>();
            // 将所有的元素加入到map中，重复元素只保留一份
            for (int i = 0; i < nums.length; i++) {
                map.put(nums[i], i);
            }
            // 初始化并查集， 并查集存储的是  元素的下标之间关联关系， 而不是元素本身
            UF uf = new UF(nums.length);
            // 遍历Map
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int value = entry.getKey();     // 这里是获取 nums[i] 的值
                int index = entry.getValue();   // 这里是获取 nums[i] 对应的下标
                if (map.containsKey(value + 1)) {  // 存在  value， value + 1, 连续子串
                    uf.union(index, map.get(value + 1));    //  将value， value + 1 对应的下标进行合并
                }

                if (map.containsKey(value - 1)) {
                    uf.union(index, map.get(value - 1));
                }
            }
            return uf.max;
        }
        class UF {
            int count[];
            int parent[];
            int max = 1;    // 记录最大连续 数量
            public UF (int n) {
                this.count = new int[n];
                this.parent = new int[n];
                Arrays.fill(count, 1);
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                }
            }

            public int find(int x) {
                while (x != parent[x]) {
                    // 路径压缩
                    parent[x] = parent[parent[x]];
                    x = parent[x];
                }
                return x;
            }

            public void union(int p, int q) {
                int rootP = find(p);
                int rootQ = find(q);
                if (rootP == rootQ) {
                    return;
                }

                // 使树保持平衡
                if (count[rootP] > count[rootQ]) {
                    parent[rootQ] = rootP;
                    count[rootP] += count[rootQ];
                    max = Math.max(count[rootP], max);
                } else {
                    parent[rootP] = rootQ;
                    count[rootQ] += count[rootP];
                    max = Math.max(count[rootQ], max);
                }
            }
        }
    }


}
